﻿//////////////////////////////////////////////////////////////////
//
// Helen\Main.cs
//
// Copyright (c) 2012 Dan Pike.
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation files
// (the "Software"), to deal in the Software without restriction,
// including without limitation the rights to use, copy, modify, merge,
// publish, distribute, sublicense, and/or sell copies of the Software,
// and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included
// in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
// TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
// SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
using Ionic.Zlib;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using Utilities;
using System.IO;
using System.Text.RegularExpressions;
using System.Diagnostics;

using Rectangle = System.Drawing.Rectangle;
using System.Threading;

namespace Helen
{
   public partial class Main : Form
   {
      private static Logger logger_;
      private int missingCount_;
      private int failedCount_;
      private int processed_;
      private Thread[] threads_;
      private const Int32 MAGIC_HEIGHTS = 0x27258421;
      private const Int32 MAGIC_NORMALS = 0x15354774;

      delegate string Processor(CellCursor cellCursor);

      private class CellCursor
      {
         public ListViewItem Item;
         public bool HaveHeights;
         public bool HaveNormals;
         public int Latitude;
         public int Longitude;
         public Cell[,] Cells;
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      static Main()
      {
         logger_ = Program.Logger;
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      public Main()
      {
         InitializeComponent();
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private void exitToolStripMenuItem_Click(object sender, EventArgs e)
      {
         Close();
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private void Main_FormClosing(object sender, FormClosingEventArgs e)
      {
         try
         {
            Program.Settings.WindowState.Value = WindowState;
            if (FormWindowState.Normal == WindowState)
            {
               Program.Settings.Window.Value = new Rectangle(Left, Top, Width, Height);
            }
            else
            {
               Program.Settings.Window.Value = new Rectangle(0, 0, 0, 0);
            }
         }
         catch (System.Exception ex)
         {
            logger_.Exception(ex);
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private void Main_FormClosed(object sender, FormClosedEventArgs e)
      {
         cancelConversionToolStripMenuItem_Click(null, null);
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private void Main_Load(object sender, EventArgs e)
      {

      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private void convertToolStripMenuItem_Click(object sender, EventArgs e)
      {
         try
         {
            missingCount_ = 0;
            failedCount_ = 0;

            statusBar.Text = "Running";
            threads_ = new Thread[2];
            Queue<Tuple<int, int>> positions = new Queue<Tuple<int, int>>();
            for (int lat = 49; 24 <= lat; --lat)
            {
               for (int lon = -126; -67 >= lon; ++lon)
               {
                  positions.Enqueue(new Tuple<int, int>(lat, lon));
               }
            }
            for (int threadIndex = 0; threadIndex < threads_.Length; ++threadIndex)
            {
               threads_[threadIndex] = new Thread(new ThreadStart(() => processFiles(positions)));
               threads_[threadIndex].Name = "pool #" + threadIndex;
               threads_[threadIndex].Start();
            }
         }
         catch (System.Exception ex)
         {
            logger_.Exception(ex);
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      private void processFiles(Queue<Tuple<int, int>> positions)
      {
         string result;
         Tuple<int, int> position;
         Stopwatch sw = new Stopwatch();
         CellCursor cellCursor = new CellCursor();
         cellCursor.Cells = new Cell[3602, 3602];

         processed_ = 0;
         while (true)
         {
            lock (positions)
            {
               if (0 == positions.Count)
               {
                  break;
               }
               position = positions.Dequeue();
            }
            int lat = position.Item1;
            int lon = position.Item2;

            sw.Restart();
            cellCursor.Latitude = lat;
            cellCursor.Longitude = lon;

            // Look for existing files
            checkHeightsFile(cellCursor);
            checkNormalsFile(cellCursor);

            if ((cellCursor.HaveHeights && cellCursor.HaveNormals)
               || !loadFile(cellCursor))
            {
               // We already have this location mapped out or
               // there is no height data for it
               continue;
            }

            // Create the ListItem synchronously
            lvFiles.Invoke((MethodInvoker)(() =>
            {
               cellCursor.Item = lvFiles.Items.Insert(0, string.Format("N{0:00}W{1:000}", lat, -lon));
               for (int index = 1; index < lvFiles.Columns.Count; ++index)
               {
                  cellCursor.Item.SubItems.Add(string.Empty);
               }
            }));

            logger_.DebugFormat("loading took {0}ms", sw.ElapsedMilliseconds);
            sw.Restart();

            result = clearSea(cellCursor);
            SafeAsyncInvoker.BeginInvoke(lvFiles, () => { cellCursor.Item.SubItems[1].Text = result; });
            logger_.DebugFormat("zeroing the sea took {0}ms", sw.ElapsedMilliseconds);
            sw.Restart();

            result = fillMissingVertices(cellCursor);
            bool fillFailed = result.Contains("giving up");
            SafeAsyncInvoker.BeginInvoke(lvFiles, () =>
            {
               cellCursor.Item.SubItems[2].Text = result;
               if (fillFailed)
               {
                  cellCursor.Item.ForeColor = System.Drawing.Color.Red;
                  statusFailed.Text = Interlocked.Increment(ref failedCount_).ToString("#,0 failed");
               }
               else if (!result.StartsWith("none"))
               {
                  cellCursor.Item.ForeColor = System.Drawing.Color.Blue;
                  statusMissing.Text = Interlocked.Increment(ref missingCount_).ToString("#,0 missing");
                        
               }
            });
            logger_.DebugFormat("missing vertices took {0} ms", sw.ElapsedMilliseconds);
            sw.Restart();

            if (!fillFailed)
            {
               // Run it through the pipeline of processors
               Processor[] processors = new Processor[]
               {
                  calculateFaceNormals,
                  calculateVertexNormals,
                  remapCellHeights,
                  remapNormals,
               };
               int subItemIndex = 2;
               foreach (Processor processor in processors)
               {
                  processor(cellCursor);
                  result = sw.ElapsedMilliseconds.ToString("#,0 ms");
                  sw.Restart();
                  SafeAsyncInvoker.BeginInvoke(lvFiles, () => { cellCursor.Item.SubItems[++subItemIndex].Text = result; });
               }

               Interlocked.Increment(ref processed_);
               lvFiles.Invoke((MethodInvoker)(() => statusProcessed.Text = string.Format("{0} processed", processed_)));

               Array.Clear(cellCursor.Cells, 0, 3602 * 3602);
               logger_.DebugFormat("reset took {0}ms", sw.ElapsedMilliseconds);
            }
         }

         lock (this)
         {
            for (int index = 0; index < threads_.Length; ++index)
            {
               if ((Thread.CurrentThread != threads_[index]) && threads_[index].IsAlive)
               {
                  // Still processing on another thread
                  return;
               }
            }
         }
         SafeAsyncInvoker.BeginInvoke(lvFiles, () => { statusBar.Text = "Ready"; });         
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="cellCursor"></param>
      private void checkHeightsFile(CellCursor cellCursor)
      {
         string filename = Path.Combine(Program.Settings.CellFolder.Value,
            string.Format("N{0:00}W{1:000}.heights", cellCursor.Latitude, -cellCursor.Longitude));
         if (!File.Exists(filename))
         {
            cellCursor.HaveHeights = false;
         }
         else
         {
            using (Stream stream = new FileStream(filename, FileMode.Open,
               FileAccess.Read, FileShare.None, 8))
            {
               BinaryReader reader = new BinaryReader(stream);
               cellCursor.HaveHeights = (MAGIC_HEIGHTS == reader.ReadInt32());
            }
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="cellCursor"></param>
      private void checkNormalsFile(CellCursor cellCursor)
      {
         string filename = Path.Combine(Program.Settings.CellFolder.Value,
            string.Format("N{0:00}W{1:000}.normals", cellCursor.Latitude, -cellCursor.Longitude));
         if (!File.Exists(filename))
         {
            cellCursor.HaveNormals = false;
         }
         else
         {
            using (Stream stream = new FileStream(filename, FileMode.Open,
               FileAccess.Read, FileShare.None, 8))
            {
               BinaryReader reader = new BinaryReader(stream);
               cellCursor.HaveNormals = (MAGIC_NORMALS == reader.ReadInt32());
            }
         }
      }
      
      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="lat"></param>
      /// <param name="lon"></param>
      private bool loadFile(CellCursor cellCursor)
      {
         // Do we have data for this, or is it in the middle of the ocean?
         string filename = Path.Combine(Program.Settings.Folder.Value,
            string.Format("N{0:00}W{1:000}.hgt", cellCursor.Latitude, -cellCursor.Longitude));
         if (!File.Exists(filename))
         {
            //logger_.DebugFormat("N{0} W{1} has no height data", cellCursor.lat, -cellCursor.lon);
            return false;
         }

         logger_.DebugFormat("Mapping N{0} W{1}", cellCursor.Latitude, -cellCursor.Longitude);
         Stream stream = new FileStream(filename, FileMode.Open);
         using (stream)
         {
            BinaryReader reader = new BinaryReader(stream);
            for (int y = 0; y < 3601; ++y)
            {
               for (int x = 0; x < 3601; ++x)
               {
                  short height = System.Net.IPAddress.NetworkToHostOrder(reader.ReadInt16());
                  Debug.Assert((-32768 == height) || ((-200 < height) && (5000 > height)));
                  cellCursor.Cells[y + 1, x + 1].Height = height;
               }
            }
         }

         // Import the top row from the file to the north, if it exists
         filename = string.Format("N{0:00}W{1:000}.hgt", cellCursor.Latitude + 1, -cellCursor.Longitude);
         if (File.Exists(filename))
         {
            using (stream = new FileStream(filename, FileMode.Open))
            {
               BinaryReader reader = new BinaryReader(stream);
               stream.Seek(3601 * 3600 * 2, SeekOrigin.Begin);
               for (int x = 0; x < 3601; ++x)
               {
                  short height = System.Net.IPAddress.NetworkToHostOrder(reader.ReadInt16());
                  cellCursor.Cells[0, x + 1].Height = height;
               }
            }
         }
         else
         {
            // Copy the values from the next row. We only need these values to
            // calculate normals
            for (int x = 0; x < 3602; ++x)
            {
               cellCursor.Cells[0, x].Height = cellCursor.Cells[1, x].Height;
            }
         }

         // Import the left column from the file to the west
         filename = string.Format("N{0:00}W{1:000}.hgt", cellCursor.Latitude, -(1 + cellCursor.Longitude));
         if (File.Exists(filename))
         {
            using (stream = new FileStream(filename, FileMode.Open))
            {
               BinaryReader reader = new BinaryReader(stream);
               for (int y = 0; y < 3601; ++y)
               {
                  stream.Seek((3601 * y + 3600) * 2, SeekOrigin.Begin);
                  short height = System.Net.IPAddress.NetworkToHostOrder(reader.ReadInt16());
                  cellCursor.Cells[y, 0].Height = height;
               }
            }
         }
         else
         {
            // Copy the values from the next column. We only need these values to
            // calculate normals
            for (int y = 0; y < 3602; ++y)
            {
               cellCursor.Cells[y, 0].Height = cellCursor.Cells[y, 1].Height;
            }
         }
         return true;
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="lat"></param>
      /// <param name="lon"></param>
      private string clearSea(CellCursor cellCursor)
      {
         // If there is no file to the east or west, then we assume that "unknown"
         // on the east and west boundaries means "ocean" at height == 0
         bool oceanWest = !File.Exists(Path.Combine(Program.Settings.Folder.Value,
            string.Format("N{0:00}W{1:000}.hgt", cellCursor.Latitude, -(1 + cellCursor.Longitude))));
         bool oceanEast = !File.Exists(Path.Combine(Program.Settings.Folder.Value,
            string.Format("N{0:00}W{1:000}.hgt", cellCursor.Latitude, 1 - cellCursor.Longitude)));
         bool oceanSouth = !File.Exists(Path.Combine(Program.Settings.Folder.Value,
            string.Format("N{0:00}W{1:000}.hgt", cellCursor.Latitude - 1, -cellCursor.Longitude)));
         bool oceanNorth = !File.Exists(Path.Combine(Program.Settings.Folder.Value,
            string.Format("N{0:00}W{1:000}.hgt", cellCursor.Latitude + 1, -cellCursor.Longitude)));
         if (!oceanEast && !oceanWest && !oceanSouth && !oceanNorth)
         {
            // Nothing to do
            return "none";
         }

         int seaCount = 0;
         if (oceanEast)
         {
            for (int y = 0; y < 3601; ++y)
            {
               for (int x = 0; x < 3601; ++x)
               {
                  if (-32768 == cellCursor.Cells[y, x].Height)
                  {
                     cellCursor.Cells[y, x].Height = 0;
                     seaCount++;
                  }
                  else
                  {
                     // We hit the edge of something
                     break;
                  }
               }
            }
         }
         if (oceanWest)
         {
            for (int y = 0; y < 3601; ++y)
            {
               for (int x = 3601; 0 <= x; --x)
               {
                  if (-32768 == cellCursor.Cells[y, x].Height)
                  {
                     cellCursor.Cells[y, x].Height = 0;
                     seaCount++;
                  }
                  else
                  {
                     // We hit the edge of something
                     break;
                  }
               }
            }
         }
         if (oceanSouth)
         {
            for (int x = 0; 3601 > x; ++x)
            {
               for (int y = 3601; 0 <= y; --y)
               {
                  if (-32768 == cellCursor.Cells[y, x].Height)
                  {
                     cellCursor.Cells[y, x].Height = 0;
                     seaCount++;
                  }
                  else
                  {
                     // We hit the edge of something
                     break;
                  }
               }
            }
         }
         if (oceanNorth)
         {
            for (int x = 0; 3601 > x; ++x)
            {
               for (int y = 0; 3601 >= y; ++y)
               {
                  if (-32768 == cellCursor.Cells[y, x].Height)
                  {
                     cellCursor.Cells[y, x].Height = 0;
                     seaCount++;
                  }
                  else
                  {
                     // We hit the edge of something
                     break;
                  }
               }
            }
         }
         logger_.DebugFormat("filled {0} cells with eastern ocean={1}, western ocean={2}",
            seaCount, oceanEast, oceanWest);
         return (0 == seaCount) ? "none" : seaCount.ToString("#,0");
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="lat"></param>
      /// <param name="lon"></param>
      private string fillMissingVertices(CellCursor cellCursor)
      {
         // Read all of the missing cells into a working array
         int x, y;
         List<int> missingList = new List<int>();
         for (y = 0; y < 3602; ++y)
         {
            for (x = 0; x < 3602; ++x)
            {
               if (-32768 == cellCursor.Cells[y, x].Height)
               {
                  missingList.Add((y * 3602) + x);
               }
            }
         }
         int missingCount = missingList.Count;
         if (0 == missingCount)
         {
            // It's all there!
            return "none";
         }

         int checkEvery = 10;
         DateTime startedAt = DateTime.Now, lastMsg = startedAt;
         int originalMissing = missingCount, failedCount = 0;
         int[] missing = missingList.ToArray();
         while (true)
         {
            for (int thisIndex = 0; thisIndex < missingCount; ++thisIndex)
            {
               // Can we replace this cell value?
               int cellIndex = missing[thisIndex];
               x = cellIndex % 3602;
               y = cellIndex / 3602;

               int existingCount = 0, totalHeight = 0;
               for (int checkY = Math.Max(0, y - 1); checkY <= Math.Min(3601, y + 1); ++checkY)
               {
                  for (int checkX = Math.Max(0, x - 1); checkX <= Math.Min(3601, x + 1); ++checkX)
                  {
                     int thisHeight = cellCursor.Cells[checkY, checkX].Height;
                     if (-32768 != thisHeight)
                     {
                        totalHeight += thisHeight;
                        ++existingCount;
                     }
                  }
               }

               if (1 < existingCount)
               {
                  // There's enough to interpolate a new value for this cell
                  totalHeight += existingCount / 2; // Round it to nearest
                  cellCursor.Cells[y, x].Height = (short)(totalHeight / existingCount);
               }
               else
               {
                  // Couldn't do it this time, put it back on the queue to try again
                  // when we've done the ones that we can
                  missing[failedCount++] = cellIndex;
               }
            }

            if (missingCount == failedCount)
            {
               // Couldn't convert any of them
               break;
            }

            // Go around again for another go at them
            missingCount = failedCount;
            failedCount = 0;

            if (0 == --checkEvery)
            {
               checkEvery = 1;
               DateTime now = DateTime.Now;
               if (30 < (now - startedAt).TotalMinutes)
               {
                  return string.Format("giving up with {0} missing", missingCount);
               }
               if (1 < (now - lastMsg).TotalSeconds)
               {
                  SafeAsyncInvoker.BeginInvoke(lvFiles, () =>
                  {
                     cellCursor.Item.SubItems[2].Text = missingCount.ToString("#,0");
                  });
                  lastMsg = DateTime.Now;
               }
            }
         }
         if (0 < missingCount)
         {
            logger_.DebugFormat("{0} of {1} missing vertices still remaining",
               missingCount, originalMissing);
            for (int index = 0; index < Math.Min(10, missingCount); ++index)
            {
               y = missing[index] / 3602;
               x = missing[index] % 3602;
               logger_.DebugFormat(("   [y={0}, x={1}]"), y, x);
            }
         }
         return string.Format("{0} of {1:#,0}",
            (0 == missingCount)
               ? "none"
               : string.Concat("giving up: ", missingCount.ToString("#,0")),
            originalMissing);
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="cellCursor.cells"></param>
      /// <returns></returns>
      private string calculateFaceNormals(CellCursor cellCursor)
      {
         if (cellCursor.HaveNormals)
         {
            return "skipped";
         }
         for (int y = 0; y < 3601; ++y)
         {
            for (int x = 0; x < 3601; ++x)
            {
               Vector3 bottom = new Vector3(30.0f, 0.0f, cellCursor.Cells[y, x + 1].Height - cellCursor.Cells[y, x].Height);
               Vector3 left = new Vector3(0.0f, 30.0f, cellCursor.Cells[y + 1, x].Height - cellCursor.Cells[y, x].Height);
               cellCursor.Cells[y, x].faceNormal0 = Vector3.Cross(bottom, left);
               Debug.Assert(0 < cellCursor.Cells[y, x].faceNormal0.Z);

               Vector3 top = new Vector3(-30.0f, 0.0f, cellCursor.Cells[y + 1, x].Height - cellCursor.Cells[y + 1, x + 1].Height);
               Vector3 right = new Vector3(0.0f, -30.0f, cellCursor.Cells[y, x + 1].Height - cellCursor.Cells[y + 1, x + 1].Height);
               cellCursor.Cells[y, x].faceNormal1 = Vector3.Cross(top, right);
               Debug.Assert(0 < cellCursor.Cells[y, x].faceNormal1.Z);
            }
         }
         return "done";
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="cellCursor.cells"></param>
      /// <returns></returns>
      private string calculateVertexNormals(CellCursor cellCursor)
      {
         if (cellCursor.HaveNormals)
         {
            return "skipped";
         }
         for (int y = 0; y < 3601; ++y)
         {
            for (int x = 0; x < 3601; ++x)
            {
               cellCursor.Cells[y, x].vertexNormal =
                  ( cellCursor.Cells[y, x].faceNormal1
                  + cellCursor.Cells[y, x + 1].faceNormal0
                  + cellCursor.Cells[y, x + 1].faceNormal1
                  + cellCursor.Cells[y + 1, x + 1].faceNormal0
                  + cellCursor.Cells[y + 1, x].faceNormal1
                  + cellCursor.Cells[y + 1, x].faceNormal0
                  );
               cellCursor.Cells[y, x].vertexNormal.Normalize();
               Debug.Assert(0 < cellCursor.Cells[y, x].vertexNormal.Z);
            }
         }
         return "done";
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// Create a mapping of 8-bit value to 16-bit height based on the
      /// distribution of heights throughout the file. We assume that all
      /// heights are valid by this point, so it's safe to use the full range
      /// of 0-255.
      /// </summary>
      /// <param name="cellCursor.cells"></param>
      /// <returns></returns>
      private string remapCellHeights(CellCursor cellCursor)
      {
         if (cellCursor.HaveHeights)
         {
            return "skipped";
         }
         // Count up all the different height values
         float[] frequency = new float[65536];
         int minHeightIndex = int.MaxValue, maxHeight = int.MinValue;
         for (int y = 1; y < 3601; ++y)
         {
            for (int x = 1; x < 3601; ++x)
            {
               int offsetHeight = cellCursor.Cells[y, x].Height + 32768;
               ++frequency[offsetHeight];
               minHeightIndex = Math.Min(minHeightIndex, offsetHeight);
               maxHeight = Math.Max(maxHeight, offsetHeight);
            }
         }

         int heightIndex = 0;
         short[] heightMap = new short[256];    // The minimum height value for each code
         float[] frequencies = new float[256];  // The number of different cells using this code
         float totalRemaining = 3600.0f * 3600.0f;
         heightMap[0] = (short)(minHeightIndex - 32768);
         frequencies[0] = frequency[minHeightIndex];
         for (int trueHeightIndex = minHeightIndex + 1; trueHeightIndex < maxHeight; ++trueHeightIndex)
         {
            // Should we merge this height into the existing code, or allocate
            // a new code (based on the number of heights left and codes still available)?
            float newFrequency = frequencies[heightIndex] + frequency[trueHeightIndex];
            if (newFrequency / totalRemaining > 1.0f / (256 - heightIndex))
            {
               // That would be too many on one index, so we "fix" the number
               // of heights that use that code ...
               totalRemaining -= frequencies[heightIndex];

               // ... and allocate a new code for the next block of heights
               heightMap[++heightIndex] = (short)(trueHeightIndex - 32768);
               frequencies[heightIndex] = frequency[trueHeightIndex];
            }
            else
            {
               // There aren't enough of this height to be worth allocating
               // a new index, so combine it with the current index
               frequencies[heightIndex] += frequency[trueHeightIndex];
            }
         }

         // Output the cells
         string cellFolder = Program.Settings.CellFolder.Value;
         string cellFilename = Path.Combine(cellFolder,
            string.Format("N{0:00}W{1:000}.heights", cellCursor.Latitude, -cellCursor.Longitude));
         using (Stream stream = new FileStream(cellFilename, FileMode.Create))
         {
            BinaryWriter writer = new BinaryWriter(stream);
            writer.Write(MAGIC_HEIGHTS);  // Version number of the file
            writer.Write((Int32)12);      // Offset to the height map in the file (allows for future changes to format)
            writer.Write((Int32)536);     // Offset to the first tile in the file (allows for future changes to format)

            // First we write the height map
            for (int index = 0; index < 256; ++index)
            {
               writer.Write(heightMap[index]);
            }

            // The we write out each 60x60 tile, as distinct from the 3601x3601 that the
            // input file came in. The layout of the tiles within the whole file is the
            // same as for the cells within each tile, i.e. North-South major, West-East
            // minor. This makes it easier to retrieve individual tiles when we read the
            // file back in - no need to Seek() all the time
            for (int offsetY = 0; offsetY < 3600; offsetY += 60)
            {
               for (int offsetX = 0; offsetX < 3600; offsetX += 60)
               {
                  for (int y = 0; y < 60; ++y)
                  {
                     for (int x = 0; x < 60; ++x)
                     {
                        short height = cellCursor.Cells[offsetY + y, offsetX + x].Height;

                        int minIndex = 0, maxIndex = heightIndex, midIndex;
                        Debug.Assert(height >= heightMap[0]);

                        while (true)
                        {
                           midIndex = (maxIndex + minIndex) / 2;
                           Debug.Assert(heightIndex >= midIndex);
                           if ((midIndex == heightIndex) ||   // It's the highest in the file
                              ((height >= heightMap[midIndex]) && (height < heightMap[midIndex + 1])))
                           {
                              writer.Write((byte)midIndex);
                              break;
                           }
                           else if (height < heightMap[midIndex])
                           {
                              maxIndex = (byte)(midIndex - 1);
                           }
                           else
                           {
                              minIndex = (byte)(midIndex + 1);
                           }
                        }
                     }
                  }
               }
            }
         }

         return "done";
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// Convert the 3xfloat values for each of the normals into 3x7-bit
      /// integers, so that we can combine these into a single 16-bit value
      /// (one of the 7-bit values will be max'ed out). The 16-bit output is
      /// formatted according to the following key. Note that Z will always
      /// be positive - there are no overhangs or vertical slopes in the maps.
      /// 
      ///       bits 15, 14         bits 12-6            bits 5-0
      /// ---------------------------------------------------------------------
      ///  0:  000 -> X is +127, Y is bits 12-6, Z is bits 5-0 (always +ve)
      ///  1:  001 -> X is -127, Y is bits 12-6, Z is bits 5-0 (always +ve)
      ///  2:  010 -> Y is +127, X is bits 12-6, Z is bits 5-0 (always +ve)
      ///  3:  011 -> Y is -127, X is bits 12-6, Z is bits 5-0 (always +ve)
      ///  4:  10  -> Z is +127, X is bits 13-7, Y is bits 6-0
      ///  5:  11  -> not used
      /// 
      /// </summary>
      /// <param name="cellCursor.cells"></param>
      /// <returns></returns>
      private string remapNormals(CellCursor cellCursor)
      {
         if (cellCursor.HaveNormals)
         {
            return "skipped";
         }
         ushort[, ,] compressed = new ushort[3601, 3601, 3];
         for (int y = 1; y <= 3601; ++y)
         {
            for (int x = 1; x <= 3601; ++x)
            {
               compressed[y - 1, x - 1, 0] = encodeNormal(cellCursor.Cells[y, x].faceNormal0);
               compressed[y - 1, x - 1, 1] = encodeNormal(cellCursor.Cells[y, x].faceNormal1);
               compressed[y - 1, x - 1, 2] = encodeNormal(cellCursor.Cells[y, x].vertexNormal);
            }
         }
         
         ThreadPool.QueueUserWorkItem((st) => writeRemapNormals(cellCursor.Latitude, cellCursor.Longitude, compressed));
         return "done";
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private ushort encodeNormal(Vector3 normal)
      {
         short xOrd = 0, yOrd = 0, zOrd = 0;
         ushort encoding = 0;

         normal.Normalize();
         float absX = Math.Abs(normal.X);
         float absY = Math.Abs(normal.Y);

         Debug.Assert(0.0 < normal.Z); // Compression algo requires +ve Z
         int caseStudy = -1;
         if (normal.Z > absY)
         {
            if (normal.Z > absX)
            {
               caseStudy = 4;
            }
            else
            {
               caseStudy = (0.0f <= normal.X) ? 0 : 1;
            }
         }
         else if (absY > absX)
         {
            caseStudy = (0.0f <= normal.Y) ? 2 : 3;
         }
         else
         {
            caseStudy = (0.0f <= normal.X) ? 0 : 1;
         }

         switch (caseStudy)
         {
            case 0:
               xOrd = 127;
               yOrd = (short)((normal.Y / absX) * 127.0f);
               zOrd = (short)((normal.Z / absX) * 127.0f);
               encoding = (ushort)(0x0000 | ((yOrd << 6) & 0x1fc0) | (zOrd & 0x3f));
               break;

            case 1:
               xOrd = -127;
               yOrd = (short)((normal.Y / absX) * 127.0f);
               zOrd = (short)((normal.Z / absX) * 127.0f);
               encoding = (ushort)(0x2000 | ((yOrd << 6) & 0x1fc0) | (zOrd & 0x3f));
               break;

            case 2:
               xOrd = (short)((normal.X / absY) * 127.0f);
               yOrd = 127;
               zOrd = (short)((normal.Z / absY) * 127.0f);
               encoding = (ushort)(0x4000 | ((xOrd << 6) & 0x1fc0) | (zOrd & 0x3f));
               break;

            case 3:
               xOrd = (short)((normal.X / absY) * 127.0f);
               yOrd = -127;
               zOrd = (short)((normal.Z / absY) * 127.0f);
               encoding = (ushort)(0x6000 | ((xOrd << 6) & 0x1fc0) | (zOrd & 0x3f));
               break;

            case 4:
               xOrd = (short)((normal.X / normal.Z) * 127.0f);
               yOrd = (short)((normal.Y / normal.Z) * 127.0f);
               zOrd = 127;
               encoding = (ushort)(0xc000 | ((xOrd << 7) & 0x3f80) | (yOrd & 0x7f));
               break;

            case 5:
            default:
               throw new InvalidOperationException("unknown/unexpected case type ("
                  + caseStudy.ToString() + ") for remapNormals())");
         }

#if false
         Vector3 check = new Vector3((float)xOrd, (float)yOrd, (float)zOrd);
         check.Normalize();
         float dot = Vector3.Dot(check, normal);
         Debug.Assert(0.9999f < dot);
#endif
         return encoding;
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="lat"></param>
      /// <param name="lon"></param>
      /// <param name="compressed"></param>
      private void writeRemapNormals(int lat, int lon, ushort[, ,] compressed)
      {
         // Output the compressed normals
         string cellFolder = Program.Settings.CellFolder.Value;
         string cellFilename = Path.Combine(cellFolder, string.Format("N{0:00}W{1:000}.normals", lat, -lon));
         using (Stream stream = new FileStream(cellFilename, FileMode.Create))
         {
            BinaryWriter writer = new BinaryWriter(stream);
            writer.Write(MAGIC_NORMALS);  // Version number of the file
            writer.Write((Int32)8);       // Offset to the first tile in the file (allows for future changes to format)

            // Then we write out three sets of normals for the 60x60 tiles. The two face
            // normals next to each other and the vertex normals as a separate tile
            for (int offsetY = 0; offsetY < 3600; offsetY += 60)
            {
               for (int offsetX = 0; offsetX < 3600; offsetX += 60)
               {
                  for (int y = 0; y < 60; ++y)
                  {
                     for (int x = 0; x < 60; ++x)
                     {
                        // faceNormal0
                        writer.Write(compressed[offsetY + y, offsetX + x, 0]);

                        // faceNormal1
                        writer.Write(compressed[offsetY + y, offsetX + x, 1]);
                     }
                  }
                  for (int y = 0; y < 61; ++y)
                  {
                     for (int x = 0; x < 61; ++x)
                     {
                        // vertexNormal
                        writer.Write(compressed[offsetY + y, offsetX + x, 2]);
                     }
                  }
               }
            }
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private void Main_Shown(object sender, EventArgs e)
      {
         try
         {
            Rectangle client = Program.Settings.Window.Value;
            if ((0 < client.Width) && (0 < client.Height))
            {
               WindowState = Program.Settings.WindowState;
               if (FormWindowState.Normal == WindowState)
               {
                  Left = client.Left;
                  Top = client.Top;
                  Width = client.Width;
                  Height = client.Height;
               }
            }
         }
         catch (System.Exception ex)
         {
            logger_.Exception(ex);
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private void folderToolStripMenuItem_Click(object sender, EventArgs e)
      {
         FolderBrowserDialog dlg = new FolderBrowserDialog();
         dlg.Description = "Select the folder containing the SRTM files to convert";
         dlg.SelectedPath = Program.Settings.Folder.Value;
         if (DialogResult.OK == dlg.ShowDialog(this))
         {
            Program.Settings.Folder.Value = dlg.SelectedPath;
         }
      }

      ////////////////////////////////////////////////////////////////////////
      /// <summary>
      /// 
      /// </summary>
      /// <param name="sender"></param>
      /// <param name="e"></param>
      private void cancelConversionToolStripMenuItem_Click(object sender, EventArgs e)
      {
         if (null != threads_)
         {
            threads_.ToList()
               .ForEach(thread =>
               {
                  try
                  {
                     if (null != thread)
                     {
                        thread.Abort();
                     }
                  }
                  catch (Exception)
                  {
                  }
               });
         }
      }
   }
}
